from typing import *
from leetcode.editor.common.node import *


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def matrixBlockSum(self, mat, k):
        #先维护一个前缀和矩阵
        m = len(mat)
        n = len(mat[0])
        preNums = [ [0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                preNums[i][j] = preNums[i-1][j]+preNums[i][j-1]+mat[i-1][j-1]-preNums[i-1][j-1]

        # 上边维护了一个前缀和
        # 开始计算边界
        result =  [ [0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                # 左上角坐标
                x1 = max(0,i-k)
                y1 = max(0,j-k)
                x2 = min(m-1,i+k)
                y2 = min(n-1,j+k)
                result[i][j] =(preNums[x2+1][y2+1]
                               -preNums[x1][y2+1]
                               -preNums[x2+1][y1]+preNums[x1][y1])
        return result

    def check(self,m,data):
        if data <0 :
            return 0
        elif data >m-1:
            return m-1
        else:
            return data
# leetcode submit region end(Prohibit modification and deletion)


#if __name__ == '__main__':
 # --  solution = Solution()
    # your test code here